
@article{NanongkaiDP-Arxiv11,
  author    = {Danupon Nanongkai and
               Atish {Das Sarma} and
               Gopal Pandurangan},
  title     = {A Tight Lower Bound on Distributed Random Walk Computation},
  journal   = {CoRR},
  volume    = {abs/1102.2906},
  year      = {2011},
  ee        = {http://arxiv.org/abs/1102.2906},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{FeigenbaumKMSZ08,
  author    = {Joan Feigenbaum and
               Sampath Kannan and
               Andrew McGregor and
               Siddharth Suri and
               Jian Zhang 0004},
  title     = {{Graph Distances in the Data-Stream Model}},
  journal   = {SIAM J. Comput.},
  volume    = {38},
  number    = {5},
  year      = {2008},
  pages     = {1709-1727},
  ee        = {http://dx.doi.org/10.1137/070683155},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in SODA'05}
}

@inproceedings{DasSarmaNP09,
  author    = {Atish {Das Sarma} and
               Danupon Nanongkai and
               Gopal Pandurangan},
  title     = {{Fast distributed random walks}},
  booktitle = {PODC},
  year      = {2009},
  pages     = {161-170},
  ee        = {http://doi.acm.org/10.1145/1582716.1582745},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{JainRS03,
  author    = {Rahul Jain and
               Jaikumar Radhakrishnan and
               Pranab Sen},
  title     = {{A Direct Sum Theorem in Communication Complexity via Message
               Compression}},
  booktitle = {ICALP},
  year      = {2003},
  pages     = {300-315},
  ee        = {http://link.springer.de/link/service/series/0558/bibs/2719/27190300.htm},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


article{DasSarmaHKKNPPW10,
  author    = {Atish {Das Sarma} and
               Stephan Holzer and
               Liah Kor and
               Amos Korman and
               Danupon Nanongkai and
               Gopal Pandurangan and
               David Peleg and
               Roger Wattenhofer},
  title     = {{Distributed Verification and Hardness of Distributed Approximation}},
  journal   = {CoRR},
  volume    = {abs/1011.3049},
  year      = {2010},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{DasSarmaHKKNPPW10,
  author    = {Atish {Das Sarma} and
               Stephan Holzer and
               Liah Kor and
               Amos Korman and
               Danupon Nanongkai and
               Gopal Pandurangan and
               David Peleg and
               Roger Wattenhofer},
  title     = {{Distributed Verification and Hardness of Distributed Approximation}},
  booktitle = {STOC},
  year      = {2011}
}



@inproceedings{DasSarmaNPT-PODC10,
  author    = {Atish {Das Sarma} and
               Danupon Nanongkai and
               Gopal Pandurangan and
               Prasad Tetali},
  title     = {{Efficient distributed random walks with applications}},
  booktitle = {PODC},
  year      = {2010},
  pages     = {201-210},
  ee        = {http://doi.acm.org/10.1145/1835698.1835745},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{WuLBCRT99,
  author    = {Bang Ye Wu and
               Giuseppe Lancia and
               Vineet Bafna and
               Kun-Mao Chao and
               R. Ravi and
               Chuan Yi Tang},
  title     = {A Polynomial-Time Approximation Scheme for Minimum Routing
               Cost Spanning Trees},
  journal   = {SIAM J. Comput.},
  volume    = {29},
  number    = {3},
  year      = {1999},
  pages     = {761-778},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in SODA'98}
}

@book{peleg,
 author = {Peleg, David},
 title = {Distributed computing: a locality-sensitive approach},
 year = {2000},
 isbn = {0-89871-464-8},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 }

@article{Luby86,
  author    = {Michael Luby},
  title     = {A Simple Parallel Algorithm for the Maximal Independent
               Set Problem},
  journal   = {SIAM J. Comput.},
  volume    = {15},
  number    = {4},
  year      = {1986},
  pages     = {1036-1053},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in STOC'85}
}

@article{Srinivasan,
  author    = {Alessandro Panconesi and
               Aravind Srinivasan},
  title     = {Randomized Distributed Edge Coloring via an Extension of
               the Chernoff-Hoeffding Bounds},
  journal   = {SIAM J. Comput.},
  volume    = {26},
  number    = {2},
  year      = {1997},
  pages     = {350-368},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {\comment{Also in PODC'92}}
}


@inproceedings{pemmaraju,
  author    = {Saurav Pandit and
               Sriram V. Pemmaraju},
  title     = {Return of the primal-dual: distributed metric facilitylocation},
  booktitle = {PODC},
  year      = {2009},
  pages     = {180-189},
  ee        = {http://doi.acm.org/10.1145/1582716.1582747},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{amos-kutten,
  author    = {Amos Korman and
               Shay Kutten},
  title     = {Distributed verification of minimum spanning trees},
  journal   = {Distributed Computing},
  volume    = {20},
  number    = {4},
  year      = {2007},
  pages     = {253-266},
  ee        = {http://dx.doi.org/10.1007/s00446-007-0025-1},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in PODC'06}
}


@article{linial,
  author    = {Nathan Linial},
  title     = {Locality in Distributed Graph Algorithms},
  journal   = {SIAM J. Comput.},
  volume    = {21},
  number    = {1},
  year      = {1992},
  pages     = {193-201},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



@inproceedings{distcomb,
author = {F. Kuhn and R. Wattenhofer},
title = {Distributed Combinatorial Optimization},
booktitle ={Technical Report 426,
Dept. of Computer Science, ETH, Zurich},
year = {2004}
}

@inproceedings{bartal,
  author    = {Yair Bartal and
               John W. Byers and
               Danny Raz},
  title     = {{Global Optimization Using Local Information with Applications
               to Flow Control}},
  booktitle = {FOCS},
  year      = {1997},
  pages     = {303-312},
  ee        = {http://computer.org/proceedings/focs/8197/81970303abs.htm},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{czygrinow,
  author    = {Andrzej Czygrinow and
               Michal Hanckowiak and
               Edyta Szymanska},
  title     = {{Distributed algorithm for approximating the maximum matching}},
  journal   = {Discrete Applied Mathematics},
  volume    = {143},
  number    = {1-3},
  year      = {2004},
  pages     = {62-71},
  ee        = {http://dx.doi.org/10.1016/j.dam.2003.10.004},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{kuhn-podc03,
  author    = {Fabian Kuhn and
               Roger Wattenhofer},
  title     = {Constant-time distributed dominating set approximation},
  journal   = {Distributed Computing},
  volume    = {17},
  number    = {4},
  year      = {2005},
  pages     = {303-310},
  ee        = {http://dx.doi.org/10.1007/s00446-004-0112-5},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in PODC'03}
}

@article{dubhashi-dom,
  author    = {Devdatt P. Dubhashi and
               Alessandro Mei and
               Alessandro Panconesi and
               Jaikumar Radhakrishnan and
               Aravind Srinivasan},
  title     = {{Fast distributed algorithms for (weakly) connected dominating
               sets and linear-size skeletons}},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {71},
  number    = {4},
  year      = {2005},
  pages     = {467-479},
  ee        = {http://dx.doi.org/10.1016/j.jcss.2005.04.002},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in SODA'03}
}

@inproceedings{matching,
  author    = {Mirjam Wattenhofer and
               Roger Wattenhofer},
  title     = {Distributed Weighted Matching},
  booktitle = {DISC},
  year      = {2004},
  pages     = {335-348},
  ee        = {http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=3274{\&}spage=335},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{Bar96,
  author    = {Yair Bartal},
  title     = {Probabilistic Approximations of Metric Spaces and Its Algorithmic
               Applications},
  booktitle = {FOCS},
  year      = {1996},
  pages     = {184-193},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@incollection{Dubhashi,
author = {Devdatt P. Dubhashi and Fabrizio Grandioni and Alessandro Panconesi},
title  = {{Distributed Algorithms via LP Duality and Randomization}},
booktitle  =  "Handbook of Approximation Algorithms and Metaheuristics",
publisher = "Chapman and Hall/CRC",
year =  2007
}

@inproceedings{Bar98,
  author    = {Yair Bartal},
  title     = {On Approximating Arbitrary Metrices by Tree Metrics},
  booktitle = {STOC},
  year      = {1998},
  pages     = {161-168},
  ee        = {http://doi.acm.org/10.1145/276698.276725},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{CCGGP98,
  author    = {Moses Charikar and
               Chandra Chekuri and
               Ashish Goel and
               Sudipto Guha and
               Serge A. Plotkin},
  title     = {Approximating a Finite Metric by a Small Number of Tree
               Metrics},
  booktitle = {FOCS},
  year      = {1998},
  pages     = {379-388},
  ee        = {http://computer.org/conferen/proceed/focs/9172/91720379abs.htm},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{CKR01-zero,
  author    = {Gruia C{\u{a}}linescu and
               Howard J. Karloff and
               Yuval Rabani},
  title     = {Approximation algorithms for the 0-extension problem},
  booktitle = {SODA},
  year      = {2001},
  pages     = {8-16},
  ee        = {http://doi.acm.org/10.1145/365411.365413},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{FHRT03,
  author    = {Jittat Fakcharoenphol and
               Chris Harrelson and
               Satish Rao and
               Kunal Talwar},
  title     = {An improved approximation algorithm for the 0-extension
               problem},
  booktitle = {SODA},
  year      = {2003},
  pages     = {257-265},
  ee        = {http://doi.acm.org/10.1145/644108.644153},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{khan-tcs,
  author    = {Maleq Khan and
               Gopal Pandurangan and
               V. S. Anil Kumar},
  title     = {A simple randomized scheme for constructing low-weight k-connected
               spanning subgraphs with applications to distributed algorithms},
  journal   = {Theor. Comput. Sci.},
  volume    = {385},
  number    = {1-3},
  year      = {2007},
  pages     = {101-114},
  ee        = {http://dx.doi.org/10.1016/j.tcs.2007.05.028},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{cocoon,
  author    = {Parinya Chalermsook and
               Jittat Fakcharoenphol},
  title     = {Simple Distributed Algorithms for Approximating Minimum
               Steiner Trees},
  booktitle = {COCOON},
  year      = {2005},
  pages     = {380-389},
  ee        = {http://dx.doi.org/10.1007/11533719_39},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{distLP,
  author    = {Christos H. Papadimitriou and
               Mihalis Yannakakis},
  title     = {Linear programming without the matrix},
  booktitle = {STOC},
  year      = {1993},
  pages     = {121-129},
  ee        = {http://doi.acm.org/10.1145/167088.167127},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@BOOK(Lynch,
 author = {Nancy Lynch},
 title = {Distributed Algorithms},
 publisher = {Morgan Kaufmann},
 year = {1996}
)

@BOOK(vazirani,
 author = {V. Vazirani},
 title = {Approximation Algorithms},
 publisher = {Springer Verlag},
 year = {2004}
)


@article{KPK,
  author = {M. Khan and G. Pandurangan and V.S.A. Kumar},
  title = {Distributed Algorithms for Constructing Approximate Minimum Spanning Trees in Wireless Sensor Networks},
  journal = {IEEE Transactions on Parallel and Distributed Systems},
  year = "2008 (in press)",
  note = {available at http://staff.vbi.vt.edu/maleq/papers/TPDS.pdf}
}


@inproceedings{awerbuch-optimal,
    author = "B. Awerbuch",
    title = "Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems",
    booktitle = "19th  STOC",
    year = "1987",
}

@incollection{gopal-survey,
author = "G. Pandurangan and M. Khan",
title  = "Theory of Communication Networks",
booktitle = {Algorithms and Theory of Computation Handbook (second edition)},
editor =  "M.J. Atallah and M. Blanton",
publisher = "CRC Press (forthcoming)",
year = "2009",
note = {available at http://www.cs.purdue.edu/homes/gopal/tcn.pdf}
}


%16
@ARTICLE(DistMst:Gallager,
 author = "Gallager, R. and Humblet, P. and Spira, P.",
 title = "A Distributed Algorithm for Minimum-Weight Spanning Trees",
 journal = "ACM Trans. on Programming Languages and Systems",
 year = "1983",
 volume = "5",
 number = "1",
 pages = "66-77"
)

%17
@article{garay-sublinear,
    author = "J. Garay and S. Kutten and D. Peleg",
    title = "A sublinear time distributed algorithm for minimum-weight spanning trees",
    journal = {SIAM J. on Computing},
    year = {1998},
    volume = {27},
    pages = {302--316}
}

@INPROCEEDINGS{Ravi,
  AUTHOR =       {B. Wu and G. Lancia and V. Bafna and K. Chao and R. Ravi and C. Tang},
  TITLE =        {A Polynomial Time Approximation Scheme for Minimum Routing Cost Spanning Trees},
  BOOKTITLE =    {9th SODA},
  YEAR =         {1998}
}


@INPROCEEDINGS{awerbuch,
  AUTHOR =       {B. Awerbuch},
  TITLE =        {Randomized Distributed Shortest Paths Algorithms},
  BOOKTITLE =    {21st STOC},
  YEAR =         {1989}
}


@article{cohen,
  author    = {Edith Cohen},
  title     = {{Size-Estimation Framework with Applications to Transitive
               Closure and Reachability}},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {55},
  number    = {3},
  year      = {1997},
  pages     = {441-453},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in FOCS'94}
}

@ARTICLE{cohen1,
  AUTHOR =       {E. Cohen and H. Kaplan},
  TITLE =        {Spatially-Decaying Aggregation Over a Network},
  JOURNAL =      {JCSS},
  YEAR =         {2007},
  volume =       {73},
  number =       {3},
  pages =        {265-288}
}

@ARTICLE{kunal,
  AUTHOR =       {J. Fakcharoenphol and S. Rao and K. Talwar},
  TITLE =        {A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics},
  JOURNAL =      {JCSS},
  YEAR =         {2004},
  volume =       {69},
  number =       {3},
  pages =        {485-497}
}

@article{elkin-faster,
  author    = {Michael Elkin},
  title     = {{A faster distributed protocol for constructing a minimum
               spanning tree}},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {72},
  number    = {8},
  year      = {2006},
  pages     = {1282-1308},
  ee        = {http://dx.doi.org/10.1016/j.jcss.2006.07.002},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in SODA'04}
}

@article{khan-disc,
  author    = {Maleq Khan and
               Gopal Pandurangan},
  title     = {{A fast distributed approximation algorithm for minimum spanning
               trees}},
  journal   = {Distributed Computing},
  volume    = {20},
  number    = {6},
  year      = {2008},
  pages     = {391-402},
  ee        = {http://dx.doi.org/10.1007/s00446-007-0047-8},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in DISC'06}
}



@BOOK(MU,
 author = "M. Mitzenmacher and E. Upfal",
 title = "Probability and Computing: Randomized Algorithms and Probabilistic Analysis",
 publisher = "Cambridge University Press",
 year = "2005"
)

@BOOK(Tel,
 author = {G. Tel},
 title = {Introduction to Distributed Algorithms},
 publisher = {Cambridge University Press},
 year = {1994}
)

@ARTICLE{peleg1,
  AUTHOR =       {D. Peleg},
  TITLE =        {A Time Optimal Leader Election algorithm in General Networks},
  JOURNAL =      {J. Parallel and Distributed Computing},
  YEAR =         {1990},
  volume =       {8},
  pages=       {96-99}
}

% Distributed Approximation

@InProceedings{kuhn-soda06,
  author =   {F. Kuhn and T. Moscibroda and R. Wattenhofer},
  title =    {{The Price of Being Near-Sighted}},
  booktitle =  {17th  SODA},
  year =     {2006}
}

@inproceedings{kuhn-podc04,
  author    = {Fabian Kuhn and
               Thomas Moscibroda and
               Roger Wattenhofer},
  title     = {What cannot be computed locally!},
  booktitle = {PODC},
  year      = {2004},
  pages     = {300-309},
  ee        = {http://doi.acm.org/10.1145/1011767.1011811},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@InProceedings{kuhn-spaa07,
  author    = {F. Kuhn and T. Moscibroda},
  title     = {{Distributed Approximation of Capacitated Dominating Sets}},
  booktitle = {19th SPAA},
  year      = {2007}
}

@article{jia02,
  author    = {Lujun Jia and
               Rajmohan Rajaraman and
               Torsten Suel},
  title     = {{An efficient distributed algorithm for constructing small
               dominating sets}},
  journal   = {Distributed Computing},
  volume    = {15},
  number    = {4},
  year      = {2002},
  pages     = {193-205},
  ee        = {http://link.springer.de/link/service/journals/00446/bibs/2015004/20150193.htm},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@InProceedings{grandoni05,
  author =       {F. Grandoni and J. K\"onemann and A. Panconesi and M. Sozio},
  title =        {Primal-Dual Based Distributed Algorithms for Vertex Cover
                  with Semi-Hard Capacities},
  booktitle =    "24th  PODC",
  year =         2005
}


@inproceedings{KhanKMPT08,
  author    = {Maleq Khan and
               Fabian Kuhn and
               Dahlia Malkhi and
               Gopal Pandurangan and
               Kunal Talwar},
  title     = {Efficient distributed approximation algorithms via probabilistic
               tree embeddings},
  booktitle = {PODC},
  year      = {2008},
  pages     = {263-272},
  ee        = {http://doi.acm.org/10.1145/1400751.1400787},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Elkin-sigact04,
  author    = {Michael Elkin},
  title     = {{Distributed approximation: a survey}},
  journal   = {SIGACT News},
  volume    = {35},
  number    = {4},
  year      = {2004},
  pages     = {40-57},
  ee        = {http://doi.acm.org/10.1145/1054916.1054931},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


article{elkin-survey,
    author = "M. Elkin",
    title = "An Overview of Distributed Approximation",
    journal = {ACM SIGACT News Distributed Computing Column},
    year = {2004},
    month = {December},
    volume = {35},
    number = {4},
    pages = {40--57}
}

@article{KuttenP98,
  author    = {Shay Kutten and
               David Peleg},
  title     = {{Fast Distributed Construction of Small $k$-Dominating
               Sets and Applications}},
  journal   = {J. Algorithms},
  volume    = {28},
  number    = {1},
  year      = {1998},
  pages     = {40-66},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in PODC'95}
}


@article{Thurimella97,
  author    = {Ramakrishna Thurimella},
  title     = {{Sub-Linear Distributed Algorithms for Sparse Certificates
               and Biconnected Components}},
  journal   = {J. Algorithms},
  volume    = {23},
  number    = {1},
  year      = {1997},
  pages     = {160-179},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in PODC'95}
}


@article{LotkerPP06,
  author    = {Zvi Lotker and
               Boaz Patt-Shamir and
               David Peleg},
  title     = {{Distributed MST for constant diameter graphs}},
  journal   = {Distributed Computing},
  volume    = {18},
  number    = {6},
  year      = {2006},
  pages     = {453-460},
  ee        = {http://dx.doi.org/10.1007/s00446-005-0127-6},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in PODC'01}
}


@inproceedings{LotkerPPP03,
  author    = {Zvi Lotker and
               Elan Pavlov and
               Boaz Patt-Shamir and
               David Peleg},
  title     = {{MST construction in $O(\log \log n)$ communication rounds}},
  booktitle = {SPAA},
  year      = {2003},
  pages     = {94-100},
  ee        = {http://doi.acm.org/10.1145/777412.777428},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Elkin05,
  author    = {Michael Elkin},
  title     = {{Computing almost shortest paths}},
  journal   = {ACM Transactions on Algorithms},
  volume    = {1},
  number    = {2},
  year      = {2005},
  pages     = {283-323},
  ee        = {http://doi.acm.org/10.1145/1103963.1103968},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in PODC'01}
}


@article{Elkin06,
  author    = {Michael Elkin},
  title     = {{An Unconditional Lower Bound on the Time-Approximation Trade-off
               for the Distributed Minimum Spanning Tree Problem}},
  journal   = {SIAM J. Comput.},
  volume    = {36},
  number    = {2},
  year      = {2006},
  pages     = {433-456},
  ee        = {http://dx.doi.org/10.1137/S0097539704441058},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in STOC'04}
}

@inproceedings{KorKP11,
  author    = {Liah Kor and
               Amos Korman and
               David Peleg},
  title     = {Tight Bounds For Distributed MST Verification},
  booktitle = {STACS},
  year      = {2011},
  pages     = {69-80},
  ee        = {http://dx.doi.org/10.4230/LIPIcs.STACS.2011.69},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


article{KorKP10,
  author    = {Liah Kor and Amos Korman and David Peleg},
  title     = {{Tight bounds for distributed MST verification}},
  journal   = {In preparation},
  year      = {2010}
}

@book{KNbook,
 author = {Eyal Kushilevitz and Noam Nisan},
 title = {{Communication complexity}},
 year = {1997},
 isbn = {0-521-56067-5},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
 }

@article{setdisj-survey,
 author = {Chattopadhyay, Arkadev and Pitassi, Toniann},
 title = {{The Story of Set Disjointness}},
 journal = {SIGACT News},
 volume = {41},
 number = {3},
 year = {2010},
 issn = {0163-5700},
 pages = {59--85},
 doi = {http://doi.acm.org/10.1145/1855118.1855133},
 publisher = {ACM},
 address = {New York, NY, USA},
 }

@article{tarjan,
  author    = {Robert Endre Tarjan},
  title     = {Applications of Path Compression on Balanced Trees},
  journal   = {J. ACM},
  volume    = {26},
  number    = {4},
  year      = {1979},
  pages     = {690-715},
  ee        = {http://doi.acm.org/10.1145/322154.322161},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{peleg-mst,
  author    = {Juan A. Garay and
               Shay Kutten and
               David Peleg},
  title     = {{A Sublinear Time Distributed Algorithm for Minimum-Weight
               Spanning Trees}},
  journal   = {SIAM J. Comput.},
  volume    = {27},
  number    = {1},
  year      = {1998},
  pages     = {302-316},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in FOCS '93}
}


@article{PelegR00,
  author    = {David Peleg and
               Vitaly Rubinovich},
  title     = {{A Near-Tight Lower Bound on the Time Complexity of Distributed
               Minimum-Weight Spanning Tree Construction}},
  journal   = {SIAM J. Comput.},
  volume    = {30},
  number    = {5},
  year      = {2000},
  pages     = {1427-1442},
  ee        = {http://epubs.siam.org/sam-bin/dbq/article/36974},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in FOCS'99}
}

@MISC{TCSStack10,
    TITLE = {{Lower Bound of Checking Graph Connectivity on Stream}},
    AUTHOR = {Srikanth (http://cstheory.stackexchange.com/users/227/srikanth)},
    HOWPUBLISHED = {http://cstheory.stackexchange.com},
    NOTE = {URL (accessed 2010-09-29): http://cstheory.stackexchange.com/questions/1763},
    EPRINT = {http://cstheory.stackexchange.com/questions/1763},
    URL = {http://cstheory.stackexchange.com/questions/1763},
}

@inproceedings{Yao77,
  author    = {Andrew Chi-Chih Yao},
  title     = {{Probabilistic Computations: Toward a Unified Measure of
               Complexity}},
  booktitle = {FOCS},
  year      = {1977},
  pages     = {222-227},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Razborov92,
  author    = {Alexander A. Razborov},
  title     = {{On the Distributional Complexity of Disjointness}},
  journal   = {Theor. Comput. Sci.},
  volume    = {106},
  number    = {2},
  year      = {1992},
  pages     = {385-390},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in ICALP'90}
}

@book{Vazirani-book,
    author = {Vazirani, Vijay V.},
    howpublished = {Hardcover},
    isbn = {3540653678},
    keywords = {algorithms},
    month = {July},
    publisher = {Springer},
    title = {Approximation Algorithms},
    year = {2001}
}


@incollection{HenzingerRR98,
 author = {Henzinger, Monika R. and Raghavan, Prabhakar and Rajagopalan, Sridhar},
 title = {Computing on data streams},
 booktitle = {External memory algorithms},
 editor = {Abello, James M. and Vitter, Jeffrey Scott},
 year = {1999},
 isbn = {0-8218-1184-3},
 pages = {107--118},
 numpages = {12},
 url = {http://portal.acm.org/citation.cfm?id=327766.327782},
 acmid = {327782},
 publisher = {American Mathematical Society},
 address = {Boston, MA, USA},
}


@article{NisanW93,
  author    = {Noam Nisan and
               Avi Wigderson},
  title     = {Rounds in Communication Complexity Revisited},
  journal   = {SIAM J. Comput.},
  volume    = {22},
  number    = {1},
  year      = {1993},
  pages     = {211-219},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note      = {Also in STOC'91}
}

@inproceedings{ElsasserS09,
  author    = {Robert Els{\"a}sser and
               Thomas Sauerwald},
  title     = {Tight Bounds for the Cover Time of Multiple Random Walks},
  booktitle = {ICALP (1)},
  year      = {2009},
  pages     = {415-426},
  ee        = {http://dx.doi.org/10.1007/978-3-642-02927-1_35},
  crossref  = {DBLP:conf/icalp/2009-1},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{broder,
 author = {A. Broder},
 title = {Generating Random Spanning Trees},
 booktitle = {FOCS},
 year = {1989}
 }

 @inproceedings{bar-ilan,
 author = {J. Bar-Ilan and D. Zernik},
 title = {Random Leaders and Random Spanning Trees},
 booktitle = {3rd International Workshop on Distributed Algorithms (later called DISC)},
 year = {1989}
 }

@article{Baala,
  author    = {Hichem Baala and
               Olivier Flauzac and
               Jaafar Gaber and
               Marc Bui and
               Tarek A. El-Ghazawi},
  title     = {A self-stabilizing distributed algorithm for spanning tree
               construction in wireless ad hoc networks},
  journal   = {J. Parallel Distrib. Comput.},
  volume    = {63},
  number    = {1},
  year      = {2003},
  pages     = {97-104},
  ee        = {http://dx.doi.org/10.1016/S0743-7315(02)00028-X},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{aldous,
  author    = {David Aldous},
  title     = {The Random Walk Construction of Uniform Spanning Trees and
               Uniform Labelled Trees},
  journal   = {SIAM J. Discrete Math.},
  volume    = {3},
  number    = {4},
  year      = {1990},
  pages     = {450-465},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



 @inproceedings{aleliunas,
 author = {R. Aleliunas and R.M. Karp and R.J. Lipton and L. Lovasz and C. Rackoff},
 title = {Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems},
 booktitle = {FOCS},
 year = {1979}
 }

 @inproceedings{goyal,
 author = {N. Goyal and L. Rademacher and S. Vempala},
 title = {Expanders via Random Spanning Trees},
 booktitle = {SODA},
 year = {2009}
 }


@inproceedings{MP,
 author = {S. Muthukrishnan and Gopal Pandurangan},
 title = {The bin-covering technique for thresholding random geometric graph properties},
 booktitle = {ACM SODA},
 year = {2005},
 note = {To appear in Journal of Computer and System Sciences.}
 }


@inproceedings{kelner-madry,
 author = {J. Kelner and A. Madry},
 title = {Faster Generation of Random Spanning Trees},
 booktitle = {IEEE FOCS},
 year = {2009}
 }

@InProceedings{mihail-topaware,
  author =   {C. Gkantsidis and G. Goel and M. Mihail and A. Saberi},
  title =    {Towards Topology Aware Networks},
  booktitle =    {IEEE INFOCOM},
  year =     {2007}
}


@incollection{dubhashi,
author = "D. Dubhashi and F. Grandioni and A. Panconesi",
title  = "Distributed Algorithms via LP Duality and Randomization",
booktitle  =  "Handbook of Approximation Algorithms and Metaheuristics",
year =  2007
}

@article{khan-disc,
 author = {M. Khan and G. Pandurangan},
 title = {A Fast Distributed Approximation Algorithm for Minimum Spanning Trees},
 journal = {Distributed Computing},
 year = {2008},
 volume = {20},
 pages = {391-402}
}

@inproceedings{khan-podc,
  author    = {Maleq Khan and
               Fabian Kuhn and
               Dahlia Malkhi and
               Gopal Pandurangan and
               Kunal Talwar},
  title     = {Efficient distributed approximation algorithms via probabilistic
               tree embeddings},
  booktitle = {PODC},
  year      = {2008},
  pages     = {263-272},
  ee        = {http://doi.acm.org/10.1145/1400751.1400787},
  crossref  = {DBLP:conf/podc/2008},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{kutten-domset,
    author = "S. Kutten and D. Peleg",
    title = "Fast distributed construction of k-dominating sets and applications",
    journal = {J. Algorithms},
    year = {1998},
    volume = {28},
    pages = {40--66}
}

@article{kempe,
author = {D. Kempe and F. McSherry},
title=  {A Decentralized Algorithm for Spectral Analysis},
 journal = {Journal of
Computer and System Sciences},
volume = {74(1)},
year = {2008},
pages = {70-83}
}


@inproceedings{BFFKRW,
  author    = {Tugkan Batu and
               Lance Fortnow and
               Eldar Fischer and
               Ravi Kumar and
               Ronitt Rubinfeld and
               Patrick White},
  title     = {Testing Random Variables for Independence and Identity},
  booktitle = {FOCS},
  year      = {2001},
  pages     = {442-451},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@Article{JS89,
  author =   {M. Jerrum and A. Sinclair},
  title =    {Approximating the permanent},
  journal =      {SIAM Journal of Computing},
  year =     {1989},
  volume =   {18},
  number =   {6},
  pages =    {1149--1178}
}

@misc{LPW,
  title={{Markov chains and mixing times}},
  author={Levin, D.A. and Y.(Yuval) Peres and Elizabeth L.(Elizabeth Lee) Wilmer},
  year={2009},
  publisher={American Mathematical Society}
}

@article{Lyons,
  author    = {Russell Lyons},
  title     = {Asymptotic Enumeration of Spanning Trees},
  journal   = {Combinatorics, Probability {\&} Computing},
  volume    = {14},
  number    = {4},
  year      = {2005},
  pages     = {491-522},
  ee        = {http://dx.doi.org/10.1017/S096354830500684X},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Vitter85,
  author    = {Jeffrey Scott Vitter},
  title     = {Random Sampling with a Reservoir},
  journal   = {ACM Trans. Math. Softw.},
  volume    = {11},
  number    = {1},
  year      = {1985},
  pages     = {37-57},
  note      = {Also appeared in FOCS'83},
  ee        = {http://doi.acm.org/10.1145/3147.3165},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@INPROCEEDINGS(mihail,
 author =     {C. Gkantsidis and  M. Mihail and A. Saberi},
 title =       {Throughput and Congestion in Power-Law Graphs},
booktitle = {SIGMETRICS},
 pages =       {148-159},
  year =     {2003}
  )

@article(dinwoodie,
author = {I. H. Dinwoodie},
title = {A Probability Inequality for the Occupation Measure of a Reversible Markov Chain},
journal = {The Annals of Applied Probability},
volume = {5(1)},
year =  {1995},
pages = {37-43}
)



@inproceedings{DNP09-podc,
  author    = {Atish {Das Sarma} and
               Danupon Nanongkai and
               Gopal Pandurangan},
  title     = {Fast distributed random walks},
  booktitle = {PODC},
  year      = {2009},
  pages     = {161-170},
  ee        = {http://doi.acm.org/10.1145/1582716.1582745},
  crossref  = {DBLP:conf/podc/2009},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@BOOK(lynch,
 author = {N. Lynch},
 title = {Distributed Algorithms},
 publisher = {Morgan Kaufmann Publishers, San Mateo, CA},
 year = {1996}
)

@article{peleg-bound,
  author    = {David Peleg and
               Vitaly Rubinovich},
  title     = {A Near-Tight Lower Bound on the Time Complexity of Distributed
               Minimum-Weight Spanning Tree Construction},
  journal   = {SIAM J. Comput.},
  volume    = {30},
  number    = {5},
  year      = {2000},
  pages     = {1427-1442},
  note      = {Also in FOCS'99},
  ee        = {http://epubs.siam.org/sam-bin/dbq/article/36974},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{frieze,
    author = "C. Cooper and A. Frieze and T. Radzik",
    title = "Multiple random walks in random regular graphs",
    booktitle = "Preprint",
    year = "2009"
}


@article{Gillman98,
  author    = {David Gillman},
  title     = {A Chernoff Bound for Random Walks on Expander Graphs},
  journal   = {SIAM J. Comput.},
  volume    = {27},
  number    = {4},
  year      = {1998},
  pages     = {1203-1220},
  ee        = {http://epubs.siam.org/sam-bin/dbq/article/26876},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{Jonasson98,
  author    = {Johan Jonasson},
  title     = {On the Cover Time for Random Walks on Random Graphs},
  journal   = {Combinatorics, Probability {\&} Computing},
  volume    = {7},
  number    = {3},
  year      = {1998},
  pages     = {265-279}
}

@inproceedings{Wilson96,
  author    = {David Bruce Wilson},
  title     = {Generating Random Spanning Trees More Quickly than the Cover
               Time},
  booktitle = {STOC},
  year      = {1996},
  pages     = {296-303},
  ee        = {http://doi.acm.org/10.1145/237814.237880}
}


@ARTICLE{JS00,
    author = {Johan Jonasson and Oded Schramm},
    title = {On the cover time of planar graphs},
    journal = {Elec. Comm. Probab},
    year = {2000},
    volume = {5},
    pages = {85-90}
}

@inproceedings{CooperF03,
  author    = {Colin Cooper and
               Alan M. Frieze},
  title     = {The cover time of sparse random graphs},
  booktitle = {SODA},
  year      = {2003},
  pages     = {140-147},
  ee        = {http://doi.acm.org/10.1145/644108.644134}
}


@inproceedings{BroderK88,
  author    = {Andrei Z. Broder and
               Anna R. Karlin},
  title     = {Bounds on the Cover Time (Preliminary Version)},
  booktitle = {FOCS},
  year      = {1988},
  pages     = {479-487}
}


@inproceedings{ChandraRRST89,
  author    = {Ashok K. Chandra and
               Prabhakar Raghavan and
               Walter L. Ruzzo and
               Roman Smolensky and
               Prasoon Tiwari},
  title     = {The Electrical Resistance of a Graph Captures its Commute
               and Cover Times (Detailed Abstract)},
  booktitle = {STOC},
  year      = {1989},
  pages     = {574-586}
}


@article{ST08,
  author    = {Rahul Sami and
               Andy Twigg},
  title     = {Lower bounds for distributed markov chain problems},
  journal   = {CoRR},
  volume    = {abs/0810.5263},
  year      = {2008},
  ee        = {http://arxiv.org/abs/0810.5263}
}

@article{AHLP01,
  author    = {Lada A. Adamic and
               Rajan M. Lukose and
               Amit R. Puniyani and
               Bernardo A. Huberman},
  title     = {Search in Power-Law Networks},
  journal   = {Physical Review},
  volume    = {64},
  year      = {2001},
  ee        = {http://arxiv.org/abs/cs.NI/0103016}
}

@inproceedings{BAS04,
  author    = {Ashwin R. Bharambe and
               Mukesh Agrawal and
               Srinivasan Seshan},
  title     = {Mercury: supporting scalable multi-attribute range queries},
  booktitle = {SIGCOMM},
  year      = {2004},
  pages     = {353-366},
  ee        = {http://doi.acm.org/10.1145/1015467.1015507}
}

@inproceedings{LCCLS02,
  author    = {Qin Lv and
               Pei Cao and
               Edith Cohen and
               Kai Li and
               Scott Shenker},
  title     = {Search and replication in unstructured peer-to-peer networks},
  booktitle = {ICS},
  year      = {2002},
  pages     = {84-95},
  ee        = {http://doi.acm.org/10.1145/514191.514206}
}

@inproceedings{GMS05,
  author    = {Christos Gkantsidis and
               Milena Mihail and
               Amin Saberi},
  title     = {Hybrid search schemes for unstructured peer-to-peer networks},
  booktitle = {INFOCOM},
  year      = {2005},
  pages     = {1526-1537},
  ee        = {http://dx.doi.org/10.1109/INFCOM.2005.1498436}
}

@inproceedings{C05,
  author    = {Brian F. Cooper},
  title     = {Quickly Routing Searches Without Having to Move Content},
  booktitle = {IPTPS},
  year      = {2005},
  pages     = {163-172},
  ee        = {http://dx.doi.org/10.1007/11558989_15}
}


@article{ZS06,
  author    = {Ming Zhong and
               Kai Shen},
  title     = {Random walk based node sampling in self-organizing networks},
  journal   = {Operating Systems Review},
  volume    = {40},
  number    = {3},
  year      = {2006},
  pages     = {49-55},
  ee        = {http://doi.acm.org/10.1145/1151374.1151386}
}

@inproceedings{KKD01,
  author    = {David Kempe and
               Jon M. Kleinberg and
               Alan J. Demers},
  title     = {Spatial gossip and resource location protocols},
  booktitle = {STOC},
  year      = {2001},
  pages     = {163-172},
  ee        = {http://doi.acm.org/10.1145/380752.380796}
}

@inproceedings{K00,
  author    = {Jon M. Kleinberg},
  title     = {The small-world phenomenon: an algorithmic perspective},
  booktitle = {STOC},
  year      = {2000},
  pages     = {163-170},
  ee        = {http://doi.acm.org/10.1145/335305.335325}
}

@inproceedings{KR04,
  author    = {David R. Karger and
               Matthias Ruhl},
  title     = {Simple efficient load balancing algorithms for peer-to-peer
               systems},
  booktitle = {SPAA},
  year      = {2004},
  pages     = {36-43},
  ee        = {http://doi.acm.org/10.1145/1007912.1007919}
}

@inproceedings{ZSS05,
  author    = {Ming Zhong and
               Kai Shen and
               Joel I. Seiferas},
  title     = {Non-uniform random membership management in peer-to-peer
               networks},
  booktitle = {INFOCOM},
  year      = {2005},
  pages     = {1151-1161},
  ee        = {http://dx.doi.org/10.1109/INFCOM.2005.1498342}
}

@article{MRRT53,
    abstract = {A general method, suitable for fast computing machines, for investigating such properties as equations of state for substances consisting of interacting individual molecules is described. The method consists of a modified Monte Carlo integration over configuration space. Results for the two-dimensional rigid-sphere system have been obtained on the Los Alamos MANIAC and are presented here. These results are compared to the free volume equation of state and to a four-term virial coefficient expansion.
    The Journal of Chemical Physics is copyrighted by The American Institute of Physics.},
    author = {Metropolis, Nicholas   and Rosenbluth, Arianna  W.  and Rosenbluth, Marshall  N.  and Teller, Augusta  H.  and Teller, Edward  },
    citeulike-article-id = {531300},
    doi = {http://dx.doi.org/10.1063/1.1699114},
    journal = {The Journal of Chemical Physics},
    keywords = {annealing, simulated},
    number = {6},
    pages = {1087--1092},
    posted-at = {2007-07-12 12:49:56},
    priority = {2},
    publisher = {AIP},
    title = {Equation of State Calculations by Fast Computing Machines},
    url = {http://dx.doi.org/10.1063/1.1699114},
    volume = {21},
    year = {1953}
}

@article{Hastings70,
    abstract = {A generalization of the sampling method introduced by Metropolis et al. (1953) is presented along with an exposition of the relevant theory, techniques of application and methods and difficulties of assessing the error in Monte Carlo estimates. Examples of the methods, including the generation of random orthogonal matrices and potential applications of the methods to numerical problems arising in statistics, are discussed. 10.1093/biomet/57.1.97},
    author = {Hastings, W. K. },
    citeulike-article-id = {1015842},
    doi = {http://dx.doi.org/10.1093/biomet/57.1.97},
    journal = {Biometrika},
    keywords = {approximate-methods, bayesian},
    month = {April},
    number = {1},
    pages = {97--109},
    posted-at = {2008-10-31 16:19:43},
    priority = {2},
    title = {Monte Carlo sampling methods using Markov chains and their applications},
    url = {http://dx.doi.org/10.1093/biomet/57.1.97},
    volume = {57},
    year = {1970}
}

@inproceedings{LawS03,
  author    = {Ching Law and
               Kai-Yeung Siu},
  title     = {Distributed Construction of Random Expander Networks},
  booktitle = {INFOCOM},
  year      = {2003},
  ee        = {http://www.ieee-infocom.org/2003/papers/52_02.PDF}
}

@book{chung,
 author = {Fan Chung},
 title = {Spectral Graph Theory},
 year = {1997},
 publisher = {American Mathematical Society},
 address = {Providence, RI, USA}
 }


@inproceedings{PK09,
  author    = {Gopal Pandurangan and Maleq Khan},
  title     = {Theory of Communication Networks},
  booktitle = {Algorithms and Theory of Computation Handbook, Second Edition},
  year      = {2009},
  PUBLISHER =    {CRC Press},
}




@inproceedings{AKL+79,
  author    = {Romas Aleliunas and
               Richard M. Karp and
               Richard J. Lipton and
               L{\'a}szl{\'o} Lov{\'a}sz and
               Charles Rackoff},
  title     = {Random Walks, Universal Traversal Sequences, and the Complexity
               of Maze Problems},
  booktitle = {FOCS},
  year      = {1979},
  pages     = {218-223}
}



@article{BFG+03,
 author = {H. Baala and O. Flauzac and J. Gaber and M. Bui and T. El-Ghazawi},
 title = {A self-stabilizing distributed algorithm for spanning tree construction in wireless ad hoc networks},
 journal = {J. Parallel Distrib. Comput.},
 volume = {63},
 number = {1},
 year = {2003},
 issn = {0743-7315},
 pages = {97--104},
 doi = {http://dx.doi.org/10.1016/S0743-7315(02)00028-X},
 publisher = {Academic Press, Inc.},
 address = {Orlando, FL, USA},
 }

@inproceedings{GoyalRV09,
  author    = {Navin Goyal and
               Luis Rademacher and
               Santosh Vempala},
  title     = {Expanders via random spanning trees},
  booktitle = {SODA},
  year      = {2009},
  pages     = {576-585},
  ee        = {http://doi.acm.org/10.1145/1496770.1496834}
}

@inproceedings{LKRG03,
  author    = {Dmitri Loguinov and
               Anuj Kumar and
               Vivek Rai and
               Sai Ganesh},
  title     = {Graph-theoretic analysis of structured peer-to-peer systems:
               routing distances and fault resilience},
  booktitle = {SIGCOMM},
  year      = {2003},
  pages     = {395-406},
  ee        = {http://doi.acm.org/10.1145/863955.863999}
}



@inproceedings{AAKKLT,
  author    = {Noga Alon and
               Chen Avin and
               Michal Kouck{\'y} and
               Gady Kozma and
               Zvi Lotker and
               Mark R. Tuttle},
  title     = {Many random walks are faster than one},
  booktitle = {SPAA},
  year      = {2008},
  pages     = {119-128},
  ee        = {http://doi.acm.org/10.1145/1378533.1378557}
}


@INPROCEEDINGS(costsens,
author = {B. Awerbuch and A. Baratz and D. Peleg},
 title = {Cost-sensitive analysis of communication protocols},
booktitle =  {  9th ACM PODC},
 pages = {177-187},
 year ={ 1990}
 )

@article{AP92,
 author = {Baruch Awerbuch and David Peleg},
 title = {Routing with polynomial communication-space trade-off},
 journal = {SIAM J. Discret. Math.},
 volume = {5},
 number = {2},
 year = {1992},
 issn = {0895-4801},
 pages = {151--162},
 doi = {http://dx.doi.org/10.1137/0405013},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 }

@inproceedings{AtishGP08,
  author    = {Atish {Das Sarma} and
               Sreenivas Gollapudi and
               Rina Panigrahy},
  title     = {Estimating PageRank on graph streams},
  booktitle = {PODS},
  year      = {2008},
  pages     = {69-78},
  ee        = {http://doi.acm.org/10.1145/1376916.1376928}
}


@book{MU-book-05,
 author = {Michael Mitzenmacher and Eli Upfal},
 title = {Probability and Computing: Randomized Algorithms and Probabilistic Analysis},
 year = {2005},
 isbn = {0521835402},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
 }

@inproceedings{IJ90,
  author    = {Amos Israeli and
               Marc Jalfon},
  title     = {Token Management Schemes and Random Walks Yield Self-Stabilizing
               Mutual Exclusion},
  booktitle = {PODC},
  year      = {1990},
  pages     = {119-131},
  ee        = {http://doi.acm.org/10.1145/93385.93409}
}


@inproceedings{BBF04,
  author    = {Thibault Bernard and
               Alain Bui and
               Olivier Flauzac},
  title     = {Random Distributed Self-stabilizing Structures Maintenance},
  booktitle = {ISSADS},
  year      = {2004},
  pages     = {231-240},
  ee        = {http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=3061{\&}spage=231}
}

@article{CTW93,
 author = {Don Coppersmith and Prasad Tetali and Peter Winkler},
 title = {Collisions among random walks on a graph},
 journal = {SIAM J. Discret. Math.},
 volume = {6},
 number = {3},
 year = {1993},
 issn = {0895-4801},
 pages = {363--374},
 doi = {http://dx.doi.org/10.1137/0406029},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 }

@article{DSW06,
  author    = {Shlomi Dolev and
               Elad Schiller and
               Jennifer L. Welch},
  title     = {Random Walk for Self-Stabilizing Group Communication in
               Ad Hoc Networks},
  journal   = {IEEE Trans. Mob. Comput.},
  volume    = {5},
  number    = {7},
  year      = {2006},
  pages     = {893-905},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/TMC.2006.104},
  note      = {also in PODC'02}
}


@inproceedings{DSW02,
  author    = {Shlomi Dolev and
               Elad Schiller and
               Jennifer L. Welch},
  title     = {Random walk for self-stabilitzing group communication in
               ad hoc networks},
  booktitle = {PODC},
  year      = {2002},
  pages     = {259},
  ee        = {http://doi.acm.org/10.1145/571825.571872}
}


@article{DT07,
  title={{Spanders: Distributed spanning expanders}},
  author={Dolev, S. and Tzachar, N.},
  journal={Dept. of Computer Science, Ben-Gurion University, TR-08-02},
  year={2007}
}


@inproceedings{Broder89,
  author    = {Andrei Z. Broder},
  title     = {Generating Random Spanning Trees},
  booktitle = {FOCS},
  year      = {1989},
  pages     = {442-447}
}


@inproceedings{BIZ89,
 author = {Judit Bar-Ilan and Dror Zernik},
 title = {Random Leaders and Random Spanning Trees},
 booktitle = {Proceedings of the 3rd International Workshop on Distributed Algorithms},
 year = {1989},
 isbn = {3-540-51687-5},
 pages = {1--12},
 publisher = {Springer-Verlag},
 address = {London, UK},
 }

@inproceedings{BBSB04,
  author    = {Marc Bui and
               Thibault Bernard and
               Devan Sohier and
               Alain Bui},
  title     = {Random Walks in Distributed Computing: A Survey},
  booktitle = {IICS},
  year      = {2004},
  pages     = {1-14},
  ee        = {http://dx.doi.org/10.1007/11553762_1}
}

@inproceedings{MG07,
  author    = {Rams{\'e}s Morales and
               Indranil Gupta},
  title     = {AVMON: Optimal and Scalable Discovery of Consistent Availability
               Monitoring Overlays for Distributed Systems},
  booktitle = {ICDCS},
  year      = {2007},
  pages     = {55},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/ICDCS.2007.87}
  }


 @article{GKM03,
 author = {Ayalvadi J. Ganesh and Anne-Marie Kermarrec and Laurent Massouli\'{e}},
 title = {Peer-to-Peer Membership Management for Gossip-Based Protocols},
 journal = {IEEE Trans. Comput.},
 volume = {52},
 number = {2},
 year = {2003},
 issn = {0018-9340},
 pages = {139--149},
 doi = {http://dx.doi.org/10.1109/TC.2003.1176982},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
 }

@inproceedings{DolevT10,
  author    = {Shlomi Dolev and
               Nir Tzachar},
  title     = {Spanders: distributed spanning expanders},
  booktitle = {SAC},
  year      = {2010},
  pages     = {1309-1314},
  ee        = {http://doi.acm.org/10.1145/1774088.1774369},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
